#include <vector>
#include <map>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
vector<string> trans(map<string,string> wdTransMap, vector<string> phrase, int N)
{
    for (int k = 0; k < N-1; k ++) {
        for (int i = 0; i < (int)phrase.size(); i ++) {
            string wd = phrase[i];
            if (wdTransMap.find(wd) != wdTransMap.end())
                phrase[i] = wdTransMap[wd];
        }
    }
    return phrase;
}
void game()
{
    int T,N,M;
    cin>>T;
    for (int t=1;t<=T;t++) {
        cin>>N>>M;
        map<string,string> wdTransMap;
        vector<string> phrase;
        string wd1,wd2;
        for (int m=0;m<M;m++){
            cin>>wd1>>wd2;
            wdTransMap[wd1] = wd2;
        }
        cin.get();
        string line;
        std::getline(cin, line);
        int last = 0;
        int pos;
        while ((pos=line.find(' ', last)) != string::npos) {
            phrase.push_back(line.substr(last, pos - last));
            last = pos + 1;
        }
        if (last != line.size())
            phrase.push_back(line.substr(last));

        phrase = trans(wdTransMap, phrase, N);
        cout<< "Case #" << t<<": ";
        cout<<phrase[0];
        for (int i=1; i<phrase.size();i++)
            cout<<" "<<phrase[i];
        if (t != T)
            cout<<endl;
    }
}
int main()
{
    game();
    return 0;
}
